package com.leetcode.partition5;

import com.leetcode.common.TreeNode;

/**
 * @author `RKC`
 * @date 2021/9/28 8:44
 */
public class LC437路径总和3 {

    public static int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        int res = dfs(root, targetSum);     //以当前节点作为根结点进行搜索
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(10, new TreeNode(5, new TreeNode(3, new TreeNode(3), new TreeNode(-2))
//                , new TreeNode(2, null, new TreeNode(1))), new TreeNode(-3, null, new TreeNode(11)));
        TreeNode root = new TreeNode(5, new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2)), null),
                new TreeNode(8, new TreeNode(13), new TreeNode(4, new TreeNode(5), new TreeNode(1))));
//        TreeNode root = new TreeNode(-2, null, new TreeNode(-3));
        System.out.println(pathSum(root, 22));
    }

    private static int dfs(TreeNode cur, int targetSum) {
        if (cur == null) return 0;
        int res = 0;
        if (cur.val == targetSum) res++;
        res += dfs(cur.left, targetSum - cur.val);
        res += dfs(cur.right, targetSum - cur.val);
        return res;
    }
}
